#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;
//打印链表元素
void SLTPrint(SLTNode* phead)
{
	SLTNode* ptmp = phead;
	while (ptmp)
	{
		printf("%d->", ptmp->data);
		ptmp = ptmp->next;
	}
	printf("NULL\n");
}
//申请新链表节点
SLTNode* SLTBuyNode(SLTDataType x)
{
	SLTNode* pnew = (SLTNode*)malloc(sizeof(SLTNode));
	if (pnew == NULL)
	{
		perror("申请节点失败");
		exit(1);
	}
	pnew->data = x;
	pnew->next = NULL;
	return pnew;
}
//寻找链表尾端的前一个结点
SLTNode** FindTailFront(SLTNode** pphead)
{
	//因为这个函数肯定是在别的函数里被引用的，能进行到这里pphead肯定不为空，就没加断言
	while ((*pphead)->next->next)
	{
		pphead = &((*pphead)->next);
	}
	return pphead;
}
//尾部插入
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);
	SLTNode* pnew = SLTBuyNode(x);
	if (*pphead && (*pphead)->next)//非单节点链表，需要找尾
	{
		pphead = FindTailFront(pphead);
		(*pphead)->next->next = pnew;
	}
	else if (*pphead == NULL)//空链表，直接赋值
	{
		(*pphead) = pnew;
	}
	else//单节点链表，给next赋值
	{
		(*pphead)->next = pnew;
	}
}
void SListDesTroy(SLTNode** pphead)
{
	assert(pphead);
	while (*pphead)//空链表根本不会进循环，函数不起任何作用，所以断言的时候就不把*pphead也丢进去，判断它是不是空链表了
	{
		assert(pphead);
		SLTNode* next = (*pphead)->next;
		free(*pphead);
		*pphead = next;
	}
}
SLTNode* Insert(SLTNode* des, SLTNode* src)
{
	SLTNode* next = des->next;
	SLTNode* ret = src->next;
	des->next = src;
	src->next = next;
	return ret;
}
SLTNode* Merge(SLTNode* phead1, SLTNode* phead2)//这是习题1的
{
	if (phead1 == NULL)
	{
		return phead2;
	}
	if (phead2 == NULL)
	{
		return phead1;
	}//若双方有任何一方没有元素，无需做任何操作，返回另一链表即可
	SLTNode* pcur1 = phead1;
	SLTNode* pcur2 = phead2;
	if ((phead1->data) > (phead2->data))
	{
		SLTNode* tmp = pcur1;
		pcur1 = pcur2;
		pcur2 = tmp;
	}
	SLTNode* ret = phead1;
	while (pcur1->next && pcur2)//循环里涉及对pcur1->next解应用,它不能为NULL
	{
		if ((pcur1->data) >= (pcur2->data))
		{
			pcur2 = pcur2->next;
		}
		else if ((pcur1->data) < (pcur2->data) && (pcur1->next->data) > (pcur2->data))
		{
			pcur2 = Insert(pcur1, pcur2);
			pcur1 = pcur1->next;
		}
		pcur1 = pcur1->next;
	}
	//对pcur1的尾节点单独处理
	if (pcur2 && (pcur1->data) < (pcur2->data))
		pcur1->next = pcur2;
	else if(pcur2 && pcur2->next && (pcur1->data) == (pcur2->data))
		pcur1->next = pcur2->next;
	return ret;
}
//如果是习题2就把上述函数换成下面这个
SLTNode* Merge(SLTNode* phead1, SLTNode* phead2)
//{
//	if (phead1 == NULL)
//	{
//		return phead2;
//	}
//	if (phead2 == NULL)
//	{
//		return phead1;
//	}//若双方有任何一方没有元素，无需做任何操作，返回另一链表即可
//	SLTNode* pcur1 = phead1;
//	SLTNode* pcur2 = phead2;
//	if ((phead1->data) > (phead2->data))
//	{
//		SLTNode* tmp = pcur1;
//		pcur1 = pcur2;
//		pcur2 = tmp;
//	}
//	SLTNode* ret = phead1;//以首节点值更小的链表为基准，插入另一链表的节点
//	while (pcur1->next && pcur2)
//	{
//		if ((pcur1->data <= pcur2->data)&&(pcur1->next->data >= pcur2->data))
//		{
//			pcur2 = Insert(pcur1, pcur2);
//		}
//		pcur1 = pcur1->next;
//	}
//	//若pcur2已经为空了，pcur1剩下的内容是有序的，不需要做任何操作
//	//而pcur1为空，pcur2却不为空时，需要把剩下的元素插到pcur1后面
//	if (pcur2)
//		pcur1->next = pcur2;
//	return ret;
//}

int main()
{
	//先自己生成三组链表
	//第一组，[1，2，3，4，5]和[3，4，5，6，7]
	SLTNode* phead1 = NULL;
	SLTNode* phead2 = NULL;
	SLTPushBack(&phead1, 1);
	SLTPushBack(&phead1, 2);
	SLTPushBack(&phead1, 3);
	SLTPushBack(&phead1, 4);
	SLTPushBack(&phead1, 5);
	SLTPushBack(&phead2, 3);
	SLTPushBack(&phead2, 4);
	SLTPushBack(&phead2, 5);
	SLTPushBack(&phead2, 6);
	SLTPushBack(&phead2, 7);
	SLTPrint(Merge(phead1, phead2));
	//第二组，[1，3，5，7，9]和[2，4，6，8，10]
	SLTNode* phead3 = NULL;
	SLTNode* phead4 = NULL;
	SLTPushBack(&phead3, 1);
	SLTPushBack(&phead3, 3);
	SLTPushBack(&phead3, 5);
	SLTPushBack(&phead3, 7);
	SLTPushBack(&phead3, 9);
	SLTPushBack(&phead4, 2);
	SLTPushBack(&phead4, 4);
	SLTPushBack(&phead4, 6);
	SLTPushBack(&phead4, 8);
	SLTPushBack(&phead4, 10);
	SLTPrint(Merge(phead3, phead4));
	//第三组，[]和[3,4,5,6,7]
	SLTNode* phead5 = NULL;
	SLTNode* phead6 = NULL;
	SLTPushBack(&phead6, 3);
	SLTPushBack(&phead6, 4);
	SLTPushBack(&phead6, 5);
	SLTPushBack(&phead6, 6);
	SLTPushBack(&phead6, 7);
	SLTPrint(Merge(phead5, phead6));
	return 0;
}